package leetcode.D300.T215;

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    // 一刷
    /*public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length-1, target = nums.length - k;
        while(left < right) {
            int mid = partition(nums, left, right);
            if(mid == target) {
                return nums[mid];
            } else if (mid < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left];
    }
    private int partition(int[] nums, int left, int right) {
        int base = nums[left];
        int i = left, j = right;
        while(i < j) {
            while(i < j && nums[j] >= base) {
                --j;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] <= base) {
                ++i;
            }
            nums[j] = nums[i];
        }
        nums[i] = base;
        return i;
    }*/

    /**
     * 二刷
     * 解法一：优先队列（小顶堆）
     */
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>((o1, o2) -> {
            return o1 - o2;
        });
        for(int i=0; i<k; ++i) {
            heap.add(nums[i]);
        }
        for(int i=k; i<nums.length; ++i) {
            if (heap.peek() < nums[i]) {
                heap.poll();
                heap.add(nums[i]);
            }
        }
        return heap.peek();
    }
}
